package com.zhupf.binaryTree;

/**
 * @author zhupf
 * @date 2023年12月08日 11:09
 * @Description
 * 124. 二叉树中的最大路径和
 */
public class MaxPathSum {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,new TreeNode(-2),new TreeNode(3));
        System.out.println(maxPathSum(root));
    }

    public static int maxPathSum(TreeNode root) {
        Info process = process(root);
        return process.max;
    }

    public static Info process(TreeNode root){
        Info info = new Info();
        if(root == null){
            return info;
        }
        Info left = process(root.left);
        Info right = process(root.right);
        info.maxVal = Math.max(Math.max(root.val + left.maxVal,root.val + right.maxVal),root.val);
        int sum = Math.max(root.val + left.maxVal,root.val + right.maxVal);
        info.max = Math.max(Math.max(Math.max(Math.max(left.max,right.max),root.val + left.maxVal+right.maxVal),root.val),sum);
        return info;

    }

    static class Info{
        private int max;

        private int maxVal;

        public Info(){
            this.max = Integer.MIN_VALUE;
            this.maxVal = 0;
        }
        public Info(int max,int maxVal){
            this.max = max;
            this.maxVal = maxVal;
        }

    }

}
